// Copyright 2011 Google Inc. All Rights Reserved.
// Author: jacobsa@google.com (Aaron Jacobs)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * A class representing a DAG, with facilities for finding subgraphs and
 * topologically sorting sets of nodes.
 *
 * This constructor accepts a set of nodes and an adjacency list. It throws an
 * error if there is a cycle in the graph or if any edge contains a node that
 * isn't in the set of nodes.
 *
 * @param {!flame.internal.StringSet} nodes
 *     The set of nodes in the graph.
 *
 * @param {!Array.<!flame.internal.GraphEdge>} edges
 *     The set of edges in the graph.
 *
 * @constructor
 */
flame.internal.DirectedAcyclicGraph = function(nodes, edges) {
  // Make sure there is no cycle in the graph.
  var cycleNode = flame.internal.findCycle(edges);
  if (cycleNode != null) {
    throw new Error('Cycle detected in graph involving node: ' + cycleNode);
  }

  // Make sure each edge contains legal nodes.
  for (var i = 0; i < edges.length; ++i) {
    var edge = edges[i];

    if (!nodes.contains(edge.fromNode)) {
      throw new Error('Unknown node: ' + edge.fromNode);
    }

    if (!nodes.contains(edge.toNode)) {
      throw new Error('Unknown node: ' + edge.toNode);
    }
  }

  /** @type{!flame.internal.StringSet} */
  this.nodes_ = nodes;

  /** @type{!Array.<flame.internal.GraphEdge>} */
  this.edges_ = edges;
};

/**
 * Sort the supplied list of nodes topologically according to the edges in the
 * graph. For each node A and B in the input, if B is reachable from A then B
 * will appear before A in the output list.
 *
 * Thus the edges in the graph model a 'depends on' relationship: if 'util'
 * depends on 'base' then 'base' will appear before 'util' in the output.
 *
 * @param {!Array.<string>} nodes
 *     The list of nodes to sort. An error will be thrown if any of these nodes
 *     is unknown.
 */
flame.internal.DirectedAcyclicGraph.prototype.sortTopologically =
    function(nodes) {
  // Make a copy of the original nodes. In the process, make sure each node is
  // known.
  var originalNodes = new flame.internal.StringSet;
  for (var i = 0; i < nodes.length; ++i) {
    var node = nodes[i];
    if (!this.nodes_.contains(node)) {
      throw new Error('Unknown node: ' + node);
    }

    originalNodes.insert(node);
  }

  // Erase the array; we'll insert back into it as we go.
  nodes.length = 0;

  // Perform a DFS, inserting a node only after its outgoing edges have been
  // traversed.
  var visited = new flame.internal.StringSet;
  var originalNodesList = originalNodes.getElements();

  for (var i = 0; i < originalNodesList.length; ++i) {
    var node = originalNodesList[i];
    this.visit_(node, originalNodes, visited, nodes);
  }
};

/**
 * Add all nodes reachable from the given node (including that node itself) to
 * the supplied set. The existing contents of the set will not be cleared, but
 * it is assumed that if a node A is already in the set, then all of the nodes
 * reachable from A are also already in the set. In particular, it is safe to
 * use this method twice to add two subgraphs from the same graph to the same
 * set.
 *
 * @param {string} node
 *     The node from which to find reachable nodes. This must be in the graph or
 *     an error will be thrown.
 *
 * @param {!flame.internal.StringSet} reachableNodes
 *     The set to emit into.
 */
flame.internal.DirectedAcyclicGraph.prototype.addReachableNodes =
    function(node, reachableNodes) {
  // Make sure this is a node that we know about.
  if (!this.nodes_.contains(node)) {
    throw new Error('Unknown node: ' + node);
  }

  // If the node has already been added, then we assume all of its reachable
  // nodes have already been added too and we are done.
  if (reachableNodes.contains(node)) {
    return;
  }

  // Add this node and recurse over all of its outgoing edges.
  reachableNodes.insert(node);
  for (var i = 0; i < this.edges_.length; ++i) {
    var edge = this.edges_[i];
    if (edge.fromNode != node) {
      continue;
    }

    this.addReachableNodes(edge.toNode, reachableNodes);
  }
};

/**
 * An implementation detail of sortTopologically. Visit nodes that haven't
 * already been visited in depth-first order, inserting the visited node in the
 * output array afterward.
 *
 * @param {string} node
 *     The node to visit.
 *
 * @param {!flame.internal.StringSet} originalNodes
 *     The nodes the user requested to be sorted. Visited nodes not in this set
 *     won't be inserted into the array.
 *
 * @param {!flame.internal.StringSet} visited
 *     Nodes already visited.
 *
 * @param {!Array.<string>} sortedNodes
 *     The user's output array of sorted nodes.
 */
flame.internal.DirectedAcyclicGraph.prototype.visit_ =
    function(node, originalNodes, visited, sortedNodes) {
  // Have we already visited this node?
  if (visited.contains(node)) {
    return;
  }

  // Record that we've visited it.
  visited.insert(node);

  // Iterate over all of the node's outgoing edges, visiting their endpoint.
  for (var i = 0; i < this.edges_.length; ++i) {
    var edge = this.edges_[i];
    if (edge.fromNode != node) {
      continue;
    }

    this.visit_(edge.toNode, originalNodes, visited, sortedNodes);
  }

  // Insert into the user's array if necessary.
  if (originalNodes.contains(node)) {
    sortedNodes.push(node);
  }
};
